In video encoding, motion estimation is one of the speed bottlenecks during encoding. A fast and accurate motion estimation method can reduce the command period (as measured by millions instructions per second) in a platform implementing video encoding.
Conventional motion estimation methods include, for example, the three-step search (TSS). The three-step search has a fixed searching pattern and its first search step can be rather imprecise. As a result, the search can easily be trapped in a local minimal value. Thus, the three-step search method can be ineffective for relatively small motion vectors.
In another example, the diamond search method is another conventional motion estimation method that is named after the shape of its searching pattern. The diamond search method is simple and effective, and is one of the best searching methods currently available. The basic principle of the diamond search method is to optimize the motion estimation speed and accuracy using the shape and size of the searching pattern. One drawback of the diamond search method is that when searching the optimal match point, if a small search pattern is used, the small search pattern can trap the search into local minimal; if a large search pattern is used, then the search might not be able to find the optimal match point. As a result, the diamond search method typically uses two sets of shapes and sizes of search patterns based on the basic principal of motion vectors in video images. The search patterns can include:
1. Large diamond search pattern (LDSP) includes nine potential positions.
2. Small diamond search pattern (SDSP) includes five potential positions.
The search process of the diamond search method is as follows: during an initial period, the large diamond search pattern is repeatedly used until the optimal matching block is located in the center of the large diamond. Because the large diamond search pattern has a long search step, the search scope can be large. Thus, the large diamond search pattern can be used as a coarse search tool to prevent the search from being trapped in a local minimal. After the coarse search is completed, it is believed the optimal point is within the diamond formed by eight points surrounding the large diamond search pattern. Then, the small diamond search pattern is used to achieve the precise location of the optimal matching block to avoid a large amount of fluctuation for improved accuracy of motion estimation. Thus, the diamond search method can be convoluted.
As described above, all of the conventional search methods have their own drawbacks. For example, none of these methods can significantly improve the encoder performance in actual semiconductor devices.